package ljl.alg.wangzheng_camp.round1.dp;

import java.util.*;

public class _139_word_break {
    
    public boolean wordBreak1(String s, List<String> wordDict) {
        int len = s.length();
        boolean[] dp = new boolean[len + 1];
        dp[0] = true;
        Set<String> words = new HashSet<>(wordDict);
        for (int i = 0; i <= len; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && words.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        
        return dp[len];
    }
    
    /**
     * 第二种写法，这种比上一种更合理一点我感觉
     * 这个少个 break，感觉上面的快啊
    * */
    public boolean wordBreak2(String s, List<String> wordDict) {
        int len = s.length();
        boolean[] dp = new boolean[len + 1];
        dp[0] = true;
        Set<String> words = new HashSet<>(wordDict);
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len + 1; j++) {
                if (dp[i] && words.contains(s.substring(i, j)))
                    dp[j] = true;
            }
        }
        return dp[len];
    }
    
    /**
     * 这个也不慢的，甚至还有点快
     * */
    public boolean wordBreak3(String s, List<String> wordDict) {
        words = new HashSet<>(wordDict);
        return dfs(s);
    }
    Map<String, Boolean> cache = new HashMap<>();
    Set<String> words;
    boolean dfs(String s) {
        if (cache.containsKey(s)) return cache.get(s);
        boolean res = s.length() == 0;
        for (int i = 0; i < s.length() + 1; i++) {
            if (words.contains(s.substring(0, i))) {
                res |= dfs(s.substring(i));
            }
        }
        cache.put(s, res);
        return res;
    }
    
    /*
    class Solution:
        def wordBreak(self, s: str, wordDict: List[str]) -> bool:
            import functools
            @functools.lru_cache(None)
            def back_track(s):
                if(not s):
                    return True
                res=False
                for i in range(1,len(s)+1):
                    if(s[:i] in wordDict):
                        res=back_track(s[i:]) or res
                return res
            return back_track(s)
    * */
    
}
